package org.ww.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序
 *      刚开始将数组看成一个有序表和一个无序表，将有序表中放一个数，然后每次从无序表中取出一个数
 *      在有序表中进行排序，找到合适的位置放入，一次类推
 */
public class InsertSort {
    public static void main(String[] args) {
        Integer[] data=new Integer[]{3,2,6,211,34,-1,23};
        insert(data);
        System.out.println("排序后的数组："+Arrays.asList(data));
    }
    public static void insert(Integer[] data){
        int insIndex=0;
        int insVal=0;
        for(int i=1;i<data.length;i++){
            insIndex=i-1;  //要进行比较的值的索引
            insVal=data[i]; //要插入的值
            while(insIndex>=0 && insVal<data[insIndex]){
                data[insIndex+1]=data[insIndex];
                insIndex--;
            }

            //进行插入
            if(insIndex+1!=i){
                data[insIndex+1]=insVal;
            }
        }

    }
}
